package leetcode_bin_tree_test;

import bin_tree.TreeNode;
import sun.reflect.generics.tree.Tree;

/**
 * 面试题 17.12. BiNode
 */
public class ConvertBiNode {
    static TreeNode head;
    public static TreeNode convertBiNode(TreeNode root) {
        // 左根右，时间复杂度O(N),空间复杂度O(N)
        // 二叉搜索树：使用中序遍历将最左边的节点设置为根结点，并且所有节点的左节点都设置为null，后序再继续遍历
//        if (root == null) {
//            return null;
//        }
//        TreeNode node = convertBiNode(root.left);
//        if (node != null) {
//            TreeNode tail = node;
//            while (tail.right != null) {
//                tail = tail.right;
//            }
//            tail.right = root;
//        }
//        root.left = null;
//        root.right = convertBiNode(root.right);
//        return node == null ? root : node;

        // 右根左，时间复杂度O(N), 空间复杂度O(1)
        if (root == null) {
            return null;
        }
        // 先遍历右边
        convertBiNode(root.right);
        // 当前节点的右子树已经连接在当前节点的右边
        // 需要将之前已经存储的右边连接到root后边
        root.right = head;
        // 更新当前以获取连接的头
        head = root;
        // 再遍历左边
        convertBiNode(root.left);
        root.left = null;
        return head;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(5);
        TreeNode n3 = new TreeNode(1);
        TreeNode n4 = new TreeNode(3);
        TreeNode n5 = new TreeNode(6);
        TreeNode n6 = new TreeNode(0);
        root.left = n1;
        root.right = n2;
        n1.left = n3;
        n1.right = n4;
        n2.right = n5;
        n3.left = n6;
        System.out.println(convertBiNode(root));
    }
}
